home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / cl182.zip / CL.CPP < prev    next >
C/C++ Source or Header  |  1993-05-15  |  24KB  |  1,167 lines
  1. /*
  2.     cl.cpp -- Container Lite v 1.82
  3.     (C) Copyright 1993  John Webster Small
  4.     All rights reserved
  5. */
  6.  
  7. #include <string.h>
  8. #include <fstream.h>
  9. #include "cl.hpp"
  10.  
  11.  
  12. char memberStreamDelimiter = '\n';
  13.  
  14. void cl::init(unsigned flags, unsigned maxNodes,
  15.     unsigned limit, unsigned delta)
  16. {
  17.     curNode = first = nodes = 0U;
  18.     cmP = voidCmP0;
  19.  
  20. /*
  21.     The following relationships are maintained
  22.     during operation of a cl:
  23.  
  24.     1 <= delta <= lowLimit <= limit <= maxNodes
  25.         <= CL_MAXNODES
  26.     lowThreshold = lowLimit - delta;
  27. */
  28.  
  29.     if (maxNodes > CL_MAXNODES)
  30.         maxNodes = CL_MAXNODES;
  31.     if (limit > maxNodes)
  32.         limit = maxNodes;
  33.     if (delta > limit)
  34.         delta = limit;
  35.     if (!delta)  {
  36.         delta = 1;
  37.         if (limit < delta)
  38.             limit = delta;
  39.         if (maxNodes < limit)
  40.             maxNodes = limit;
  41.     }
  42.     linkS = (void **)0;
  43.     this->limit = limit;
  44.     this->delta = delta;
  45.     this->maxNodes = maxNodes;
  46.     lowLimit = limit;
  47.     lowThreshold = lowLimit - delta;
  48.     this->flags = (flags | CL_SORTED);
  49. }
  50.  
  51. void cl::assign(const cl& b)
  52. {
  53.     if (flags & CL_DDELETE)
  54.         allDel();
  55.     else
  56.         allRmv();
  57.     setDelta(1); setLimit(1); setMaxNodes(1);
  58.     setMaxNodes(b.MaxNodes());
  59.     setLimit(b.Limit());
  60.     setDelta(b.Delta());
  61.     resetFlags(CL_ALL_FLAGS);
  62.     setFlags(b.Flags());
  63.     setFlags(CL_DNEW | CL_DDELETE);
  64.     setCmP(b.CmP());
  65.     for (unsigned i = 0U; i < b.Nodes(); i++)
  66.         insQNew(b.atGet(i));
  67.     setCurNode(b.CurNode());
  68. }
  69.  
  70. void cl::destruct()
  71. {
  72.     if (flags & CL_DDELETE)
  73.         allDel();
  74.     else
  75.         allRmv();
  76.     if (linkS)  {
  77.         delete linkS;
  78.         linkS = (void **)0;
  79.     }
  80. }
  81.  
  82. int cl::put(ostream& os)
  83. {
  84.     if (!(os << maxNodes << endm << limit << endm
  85.         << delta << endm << nodes << endm
  86.         << curNode << endm << flags << endm
  87.         << cmP2ID(cmP) << endm))
  88.         return 0;
  89.     for (unsigned i = 0U; i < nodes; i++)
  90.         if (!Dput(os,atGet(i)))
  91.             return 0;
  92.     return 1;
  93. }
  94.  
  95. int cl::get(istream& is)
  96. {
  97.     unsigned maxNodes, limit, delta, nodes;
  98.     unsigned curNode, flags, cmPid;
  99.  
  100.     if (!(is >> maxNodes >> nextm >> limit >> nextm
  101.         >> delta >> nextm >> nodes >> nextm
  102.         >> curNode >> nextm >> flags >> nextm
  103.         >> cmPid >> nextm))
  104.         return 0;
  105.     flags |= CL_DDELETE;
  106.     //reloaded nodes are dynamic!
  107.     setMaxNodes(maxNodes);
  108.     setLimit(limit);
  109.     setDelta(delta);
  110.     setFlags(flags);
  111.     setCmP(ID2cmP(cmPid));
  112.     void * D;
  113.     for (unsigned i = 0U; i < nodes; i++)
  114.         if (!insQ(D=Dget(is)))
  115.             if (D)  {
  116.                 Ddelete(D);
  117.                 return 0;
  118.             }
  119.     setCurNode(curNode);
  120.     return 1;
  121. }
  122.  
  123. int cl::load(const char * filename)
  124. {
  125.     int ok = 0;
  126.     allClr();
  127.     if (filename)  {
  128.         ifstream is(filename);
  129.         if (is)  {
  130.             ok = get(is);
  131.             is.close();
  132.         }
  133.     }
  134.     return ok;
  135. }
  136.  
  137. int cl::save(const char * filename)
  138. {
  139.     int ok = 0;
  140.     if (Flags(CL_DSTORE))  {
  141.         ofstream os(filename);
  142.         if (os)  {
  143.             ok = put(os);
  144.             os.close();
  145.         }
  146.     }
  147.     return ok;
  148. }
  149.  
  150. void cl::vforEach(voidApplY B, va_list args)
  151. {
  152.     if (!linkS || !B || !nodes)
  153.         return;
  154.     for (unsigned i = 0U; i < nodes; i++)
  155.         (*B)(linkS[(first+i)%limit],args);
  156. }
  157.  
  158. cl::cl(void ** argv, unsigned argc,
  159.     unsigned flags)
  160. {
  161.    init(flags,CL_MAXNODES,argc,CL_DELTA);
  162.    if (maxNodes)
  163.     if (argv)
  164.         if (argc > 0U)
  165.             while (argc--)
  166.               (void) push(argv[argc]);
  167.         else
  168.             for (argc = 0U;
  169.                 insQ(argv[argc]);
  170.                 argc++)
  171.                 /* null stmt */;
  172. }
  173.  
  174. int cl::operator==(const cl& b) const
  175. {
  176.     if (!cmP) return 0;
  177.     for (unsigned i = 0; i < nodes; i++)  {
  178.         if (i >= b.Nodes())
  179.             return 0;
  180.         if ((*cmP)(atGet(i),b.atGet(i)))
  181.             return 0;
  182.     }
  183.     if (i < b.Nodes())
  184.         return 0;
  185.     return 1;
  186. }
  187.  
  188. int cl::operator>(const cl& b) const
  189. {
  190.     if (!cmP) return 0;
  191.     unsigned c;
  192.     for (unsigned i = 0; i < nodes; i++)  {
  193.         if (i >= b.Nodes())
  194.             return 1;
  195.         if ((c = (*cmP)(atGet(i),b.atGet(i)))
  196.             != 0)
  197.             return (c > 0);
  198.     }
  199.     if (i < b.Nodes())
  200.         return -1;
  201.     return 0;
  202. }
  203.  
  204. void ** cl::vector(void ** argv, unsigned argc) const
  205. {
  206.     void ** V;
  207.  
  208.     if ((V = argv) == (void **)0)  {
  209.         if (!nodes)
  210.             return (void **)0;
  211.         if ((V = new void *[argc=nodes+1])
  212.             == (void **)0)
  213.             return (void **)0;
  214.     }
  215.     else if (argc) if (nodes > argc)
  216.         return (void **)0;
  217.     for (unsigned i = 0U; i < nodes; i++)
  218.         V[i] = atGet(i);
  219.     while (i < argc)
  220.         V[i++] = (void *)0;
  221.     return V;
  222. }
  223.  
  224. unsigned cl::setLimit(unsigned newLimit)
  225. {
  226.     void ** newLinkS;
  227.     unsigned headNodes;
  228.  
  229.     if (newLimit < nodes)
  230.         newLimit = nodes;
  231.     else if (newLimit > maxNodes)
  232.         newLimit = maxNodes;
  233.     if (newLimit < delta)
  234.         newLimit = delta;
  235.     if (!newLimit || newLimit == limit)
  236.         return 0U;
  237.     if (!linkS)
  238.         return (limit = newLimit);
  239.     if ((newLinkS = new void *[newLimit])
  240.         == (void **)0)
  241.         return 0U;
  242.     if ((headNodes = limit - first) > nodes)
  243.         headNodes = nodes;
  244.     if (headNodes)  // move leading nodes
  245.         memcpy(newLinkS,&linkS[first],
  246.             sizeof(linkS[0U])*headNodes);
  247.     /* copy wrap around trailing nodes */
  248.     if (headNodes < nodes)
  249.         memcpy(&newLinkS[headNodes],linkS,
  250.             sizeof(linkS[0U])*
  251.             (nodes-headNodes));
  252.     if (newLimit > limit)
  253.         if (newLimit - delta > limit)
  254.             lowLimit = newLimit - delta;
  255.         else
  256.             lowLimit = limit;
  257.     else
  258.         if (newLimit - delta > delta)
  259.             lowLimit = newLimit - delta;
  260.         else
  261.             lowLimit = delta;
  262.     lowThreshold = lowLimit - delta;
  263.     delete linkS;
  264.     linkS = newLinkS;
  265.     limit = newLimit;
  266.     first = 0U;
  267.     return limit;
  268. }
  269.  
  270. unsigned cl::setDelta(unsigned newDelta)
  271. {
  272.     return ((newDelta && newDelta <= lowLimit)?
  273.         delta = newDelta : 0U);
  274. }
  275.  
  276. unsigned cl::setMaxNodes(unsigned newMaxNodes)
  277. {
  278.     return ((newMaxNodes >= limit)?
  279.         (maxNodes = (newMaxNodes
  280.         > CL_MAXNODES)? CL_MAXNODES
  281.         : newMaxNodes) : 0U);
  282. }
  283.  
  284. void * cl::atIns(unsigned n, void * D)
  285. {
  286.     void ** newLinkS;
  287.     unsigned newLimit, i;
  288.  
  289.     if (!D)
  290.         return (void *)0;
  291.     if (nodes == limit)  { // no vacancy - expand
  292.         if (limit == maxNodes)
  293.             return (void *)0;
  294.         newLimit = (maxNodes - delta > limit)?
  295.             limit + delta : maxNodes;
  296.         if ((newLinkS = new void *[newLimit])
  297.             == (void **)0) //expansion unavailable
  298.             return (void *)0;
  299.         if (!Dattach(D))  {// data refuses binding
  300.             delete newLinkS;
  301.             return (void *)0;
  302.         }
  303.         newLinkS[((n <= nodes)? n : n = nodes)] = D;
  304.         // calc headNodes
  305.         if (n <= (i = limit - first))  {
  306.             // insert in head section
  307.             if (n)  {// postfix or split head
  308.                 memcpy(newLinkS,&linkS[first],
  309.                     sizeof(linkS[0U])*n);
  310.                 if (n < i) // it's a split
  311.                     memcpy(&newLinkS[n+1],
  312.                         &linkS[first+n],
  313.                         sizeof(linkS[0U])*(i-n));
  314.             }
  315.             else    // prefix head
  316.                 memcpy(&newLinkS[1],&linkS[first],
  317.                     sizeof(linkS[0U])*i);
  318.             if (i < nodes)  // copy tail
  319.                 memcpy(&newLinkS[1+i],linkS,
  320.                     sizeof(linkS[0U])
  321.                     *(nodes-i));
  322.         }
  323.         else  {    // insert in tail section
  324.             // copy head first
  325.             memcpy(newLinkS,&linkS[first],
  326.                 sizeof(linkS[0U])*i);
  327.             if (i < nodes)  { // copy tail
  328.                 memcpy(&newLinkS[i],linkS,
  329.                     sizeof(linkS[0U])*(n-i));
  330.                 if (n < nodes) // it's a tail split
  331.                     memcpy(&newLinkS[n+1],
  332.                         &linkS[n-i],
  333.                         sizeof(linkS[0U])
  334.                         *(nodes-n));
  335.             }
  336.         }
  337.         // Compute next smaller linkS size
  338.         // and threshold for shrinking.
  339.         lowLimit = limit;
  340.         lowThreshold = lowLimit - delta;
  341.         // swap new for old
  342.         delete linkS;
  343.         linkS = newLinkS;
  344.         limit = newLimit;
  345.         first = 0U;
  346.     }
  347.     else  {  // vacancy
  348.         if (!linkS)
  349.             if ((linkS = new void *[limit])
  350.                 == (void **)0)
  351.                 return (void *)0;
  352.         if (!Dattach(D))  {
  353.             if (!nodes)  {
  354.                 delete linkS;
  355.                 linkS = (void **)0;
  356.             }
  357.             return (void *)0;
  358.         }
  359.         if (!n)  // push
  360.             linkS[first? --first
  361.                 : (first = limit - 1)] = D;
  362.         else if (n >= nodes) // insQ
  363.             linkS[(first+(n=nodes))%limit] = D;
  364.         else  { // insert interior
  365.             i = (first + n) % limit;
  366.             if (i < first || !first)
  367.                 // move rear rightward
  368.                 memmove(&linkS[i+1],&linkS[i],
  369.                     sizeof(linkS[0U])
  370.                     * (nodes-n));
  371.             else  { // move front leftward
  372.                 memmove(&linkS[first-1],
  373.                     &linkS[first],
  374.                     sizeof(linkS[0U])
  375.                     *(n));
  376.                 first--;
  377.                 i--;
  378.             }
  379.             linkS[i] = D;
  380.         }
  381.     }
  382.     nodes++;
  383.     if (n <= curNode)
  384.         curNode++;
  385.     flags &= ~CL_SORTED;
  386.     return D;
  387. }
  388.  
  389.  
  390. void * cl::atInsNew(unsigned n, const void * D)
  391. {
  392.     void * cD;
  393.  
  394.     if (D && flags & CL_DNEW)
  395.         if ((cD = Dnew(D)) != (void *)0)
  396.             if (atIns(n,cD))  {
  397.                 flags |= CL_DNEWED;
  398.                 return cD;
  399.             }
  400.             else
  401.                 Ddelete(cD);
  402.     return (void *)0;
  403. }
  404.  
  405. void * cl::atRmv(unsigned n)
  406. {
  407.     void ** newLinkS = (void **)0;
  408.     unsigned newLimit, i;
  409.     void * D;
  410.  
  411.     if (!linkS || n >= nodes)
  412.         return (void *)0;
  413.     D = linkS[(((i=first+n) >=limit)? i-=limit:i)];
  414.     if (nodes <= lowThreshold) {
  415.         // get ready to contract
  416.         newLimit = lowLimit;
  417.         newLinkS = new void *[newLimit];
  418.         // Compute next smaller linkS
  419.         // size and threshold for
  420.         // shrinking.
  421.     if (nodes < delta)
  422.             lowThreshold = 0;
  423.         else
  424.             lowThreshold -= delta;
  425.         lowLimit = lowThreshold + delta;
  426.     }
  427.     if (newLinkS)  {  // remove and contract
  428.         // calc head nodes
  429.     if ((i = limit - first) > nodes)
  430.         i = nodes;
  431.         if (n < i)  {
  432.             // rmv from head section
  433.             if (n)  { // rmv from head
  434.                 memcpy(newLinkS,&linkS[first],
  435.                     sizeof(linkS[0U])*n);
  436.         if (n < i - 1)
  437.                     memcpy(&newLinkS[n],
  438.                             &linkS[first+n+1],
  439.                             sizeof(linkS[0U])*(i-n-1));
  440.             }
  441.             else    // pop head
  442.                 memcpy(newLinkS,&linkS[first+1],
  443.                     sizeof(linkS[0U])*(i-1));
  444.             if (i < nodes)  // copy tail
  445.                 memcpy(&newLinkS[i-1],linkS,
  446.                     sizeof(linkS[0U])
  447.                     *(nodes-i));
  448.         }
  449.         else  { // i <= n < nodes
  450.             // rmv from tail section
  451.             // copy head first
  452.             memcpy(newLinkS,&linkS[first],
  453.                 sizeof(linkS[0U])*i);
  454.             if (i == n)  { // pop tail
  455.                 if (n < nodes - 1)
  456.                     // copy trailing tail
  457.                     memcpy(&newLinkS[i],&linkS[1],
  458.                         sizeof(linkS[0U])*(nodes-n-1));
  459.             }
  460.             else  {  // copy up to n in tail
  461.                 memcpy(&newLinkS[i],linkS,
  462.                     sizeof(linkS[0U])*(n-i));
  463.                 // skip n'th node
  464.                 if (n < nodes - 1)
  465.                     // copy anything trailing n'th node
  466.                     memcpy(&newLinkS[n],linkS[n-i+1],
  467.                         sizeof(linkS[0U])*(nodes-n-1));
  468.             }
  469.         }
  470.         // swap new for old
  471.         delete linkS;
  472.         linkS = newLinkS;
  473.         limit = newLimit;
  474.         first = 0U;
  475.     }
  476.     else  { // simply remove
  477.         if (!n)  {  // pop
  478.             if (++first >= limit)
  479.                 first = 0U;
  480.         }
  481.         else if (n != nodes-1)  // del interior
  482.             if (i < first) // move tail leftward
  483.                 memmove(&linkS[i],&linkS[i+1],
  484.                     sizeof(linkS[0U])
  485.                     *(nodes-n-1));
  486.             else {  // move head rightward
  487.                 memmove(&linkS[first+1],
  488.                     &linkS[first],
  489.                     sizeof(linkS[0U])*n);
  490.                 first++;
  491.             }
  492.     }
  493.     if (n < curNode)
  494.         curNode--;
  495.     else if (n == curNode)
  496.         curNode = nodes-1;
  497.     if (--nodes == 0U)  {
  498.         flags |= CL_SORTED;
  499.         delete linkS;
  500.         linkS = (void **)0;
  501.     }
  502.     Ddetach(D);
  503.     return D;
  504. }
  505.  
  506. void cl::allRmv()
  507. {
  508.     flags &= ~CL_DNEWED;
  509.     while (atRmv(0U)) /* null stmt */ ;
  510. }
  511.  
  512. int  cl::atDel(unsigned n)
  513. {
  514.     void * D;
  515.  
  516.     if (flags & CL_DDELETE)
  517.         if ((D = atRmv(n)) != (void *)0)  {
  518.             Ddelete(D);
  519.             return 1;
  520.         }
  521.     return 0;
  522. }
  523.  
  524. void * cl::atDelAsg(unsigned n, void * D)
  525. {
  526.     void * S;
  527.  
  528.     if (D && flags & CL_DASSIGN
  529.         && flags & CL_DDELETE)
  530.         if ((S = atGet(n)) != (void *)0)
  531.             if (D != S)  {
  532.               (flags &= ~CL_DREAD)
  533.                 |= CL_DREAD_DEL;
  534.               if (Dassign(D,S)) {
  535.                 (void) atDel(n);
  536.                 return D;
  537.               }
  538.             }
  539.     return (void *)0;
  540. }
  541.  
  542. int cl::allDel()
  543. {
  544.     void * D;
  545.  
  546.     if (flags & CL_DDELETE)  {
  547.         while ((D = atRmv(0U)) != (void *)0)
  548.             Ddelete(D);
  549.         return 1;
  550.     }
  551.     return 0;
  552. }
  553.  
  554. void cl::allClr()
  555. {
  556.     if (flags & CL_DDELETE)
  557.         allDel();
  558.     else
  559.         allRmv();
  560. }
  561.  
  562. void * cl::atPut(unsigned n, void * D)
  563. {
  564.     if (linkS && D && (n < nodes))  {
  565.         void *& N = linkS[(first+n)%limit];
  566.         if (D != N)  if (Dattach(D))  {
  567.             flags &= ~CL_SORTED;
  568.             Ddetach(N);
  569.             if (flags & CL_DDELETE)
  570.                 Ddelete(N);
  571.             return (N=D);
  572.         }
  573.     }
  574.     return (void *)0;
  575. }
  576.  
  577. void * cl::atPutNew(unsigned n, const void * D)
  578. {
  579.     void * oldD, * cD;
  580.  
  581.     if (!D || !(flags & CL_DNEW))
  582.         return (void *)0;
  583.     if ((oldD = atGet(n)) == (void *)0)
  584.         return (void *)0;
  585.     if (oldD == D)
  586.         return (void *)0;
  587.     if ((cD = Dnew(D)) != (void *)0)
  588.         if (atPut(n,cD))  {
  589.             flags |= CL_DNEWED;
  590.             return cD;
  591.         }
  592.         else
  593.             Ddelete(cD);
  594.     return (void *)0;
  595. }
  596.  
  597. void * cl::atPutAsg(unsigned n, const void * D)
  598. {
  599.     void * oldD;
  600.  
  601.     if (D && flags & CL_DASSIGN)
  602.         if ((oldD = atGet(n)) != (void *)0)
  603.             if (D != oldD)  {
  604.                 flags &= ~(CL_DREAD
  605.                   | CL_DREAD_DEL);
  606.                 return Dassign(oldD,D);
  607.             }
  608.     return (void *)0;
  609. }
  610.  
  611. void * cl::atGet(unsigned n) const
  612. {
  613.     return ((linkS && (n < nodes))?
  614.         linkS[(first+n)%limit] : (void *)0);
  615. }
  616.  
  617. void * cl::atGetAsg(unsigned n, void * D)
  618. {
  619.     void * N;
  620.  
  621.     if (D && flags & CL_DASSIGN)
  622.         if ((N = atGet(n)) != (void *)0)
  623.             if (D != N)  {
  624.               (flags &= ~CL_DREAD_DEL)
  625.                 |= CL_DREAD;
  626.               return Dassign(D,N);
  627.             }
  628.     return (void *)0;
  629. }
  630.  
  631. void * cl::atXchg(unsigned n, void * D)
  632. {
  633.     if (linkS && D && (n < nodes))
  634.         if (Dattach(D))  {
  635.             flags &= ~CL_SORTED;
  636.             void *& N = linkS[(first+n)
  637.                 %limit];
  638.             void * oldD = N;
  639.             N = D;
  640.             Ddetach(oldD);
  641.             return oldD;
  642.         }
  643.     return (void *)0;
  644. }
  645.  
  646. unsigned cl::index(const void * D) const
  647. {
  648.     unsigned i;
  649.  
  650.     if (linkS && D)
  651.         for (i = 0U; i < nodes; i++)
  652.             if (D == linkS[(first+i)
  653.                 %limit])
  654.                 return i;
  655.     return CL_NOTFOUND;
  656. }
  657.  
  658. unsigned cl::CurNode() const
  659. {
  660.     return ((curNode < nodes)?
  661.         curNode : CL_NOTFOUND);
  662. }
  663.  
  664. int  cl::setCurNode(unsigned n)
  665. {
  666.     return ((curNode = ((n > nodes)? nodes : n))
  667.         < nodes);
  668. }
  669.  
  670. void * cl::ins(void * D)
  671. {
  672.     if (atIns(curNode+1,D))  {
  673.         if (++curNode >= nodes)
  674.             curNode = nodes - 1;
  675.         return D;
  676.     }
  677.     return (void *)0;
  678. }
  679.  
  680. void * cl::insNew(const void * D)
  681. {
  682.     void * cD;
  683.  
  684.     if (D && flags & CL_DNEW)
  685.         if ((cD = Dnew(D)) != (void *)0)
  686.             if (ins(cD))  {
  687.                 flags |= CL_DNEWED;
  688.                 return cD;
  689.             }
  690.             else
  691.                 Ddelete(cD);
  692.     return (void *)0;
  693. }
  694.  
  695. void * cl::rmv()
  696. {
  697.     void * D;
  698.     unsigned n;
  699.  
  700.     if ((D = atRmv(n=curNode)) != (void *)0)
  701.         if (n)
  702.             curNode = n - 1;
  703.         else
  704.             curNode = 0;
  705.     return D;
  706. }
  707.  
  708. int  cl::del()
  709. {
  710.     void * D;
  711.  
  712.     if (flags & CL_DDELETE)
  713.         if ((D = rmv()) != (void *)0)  {
  714.             Ddelete(D);
  715.             return 1;
  716.         }
  717.     return 0;
  718. }
  719.  
  720. void * cl::delAsg(void * D)
  721. {
  722.     void * S;
  723.  
  724.     if (D && flags & CL_DASSIGN
  725.         && flags & CL_DDELETE)
  726.         if ((S = atGet(curNode)) != (void *)0)
  727.             if (D != S)  {
  728.               (flags &= ~CL_DREAD)
  729.                 |= CL_DREAD_DEL;
  730.               if (Dassign(D,S)) {
  731.                 (void) del();
  732.                 return D;
  733.               }
  734.             }
  735.     return (void *)0;
  736. }
  737.  
  738. void * cl::next()
  739. {
  740.     if (linkS)  {
  741.         if (curNode >= nodes)
  742.             curNode = 0U;
  743.         else
  744.             curNode++;
  745.         if (curNode < nodes)
  746.             return linkS[(first+curNode)
  747.                 %limit];
  748.     }
  749.     return (void *)0;
  750. }
  751.  
  752. void * cl::nextAsg(void * D)
  753. {
  754.     unsigned oldCurNode = curNode;
  755.     void * S;
  756.  
  757.     if (D && flags & CL_DASSIGN)
  758.         if ((S = next()) != (void *)0)  {
  759.             if (D != S)  {
  760.               (flags &= ~CL_DREAD_DEL)
  761.                 |= CL_DREAD;
  762.               if (Dassign(D,S))
  763.                 return D;
  764.             }
  765.             curNode = oldCurNode;
  766.         }
  767.     return (void *)0;
  768. }
  769.  
  770. void * cl::prev()
  771. {
  772.     if (linkS)  {
  773.         if (curNode)  {
  774.             if (curNode > nodes)
  775.                 curNode = nodes;
  776.             curNode--;
  777.         }
  778.         else
  779.             curNode = nodes;
  780.         if (curNode < nodes)
  781.             return linkS[(first+curNode)
  782.                 %limit];
  783.     }
  784.     return (void *)0;
  785. }
  786.  
  787. void * cl::prevAsg(void * D)
  788. {
  789.     unsigned oldCurNode = curNode;
  790.     void * S;
  791.  
  792.     if (D && flags & CL_DASSIGN)
  793.         if ((S = prev()) != (void *)0)  {
  794.             if (D != S)  {
  795.               (flags &= ~CL_DREAD_DEL)
  796.                 |= CL_DREAD;
  797.               if (Dassign(D,S))
  798.                 return D;
  799.             }
  800.             curNode = oldCurNode;
  801.         }
  802.     return (void *)0;
  803. }
  804.  
  805. int   cl::sort(voidCmP cmP)
  806. {
  807.     unsigned low, mid, high;
  808.     unsigned d;
  809.     void * D;
  810.  
  811. /*
  812.     The current node is always reset to undefined
  813.     regardless of the outcome of sort.
  814. */
  815.  
  816.     curNode = nodes;
  817.     if (!this->cmP)
  818.         this->cmP = DcmP(voidCmP0);
  819.     if (flags & CL_SORTED)  {
  820.         if (this->cmP == cmP || !cmP)
  821.             return 1;
  822.     }
  823.     else if (!this->cmP && !cmP)
  824.         return 0;
  825.     if (cmP)  {
  826.         this->cmP = cmP;
  827.         flags &= ~CL_SORTED;
  828.     }
  829.     if (!nodes || !linkS)
  830.         return (int) (flags |= CL_SORTED);
  831.     if (first)  {
  832.         /* form contiguous block at front */
  833.         d = (first + nodes) % limit;
  834.         if (d > first)
  835.             memmove(linkS,&linkS[first],
  836.                 sizeof(linkS[0U])*nodes);
  837.         else if (d < first)
  838.             memmove(&linkS[d],
  839.                 &linkS[first],
  840.                 sizeof(linkS[0U])
  841.                 *(limit-first));
  842.         /* else array is full/contiguous */
  843.         first = 0U;
  844.     }
  845.     for (high = d = 1; d < nodes; high = ++d)  {
  846.         low = 0U;
  847.         D = linkS[d];
  848.         while (low < high)  {
  849.             mid = low +
  850.                 ((high - low) >> 1);
  851.             if ((*this->cmP)(D,
  852.                 linkS[mid]) <= 0)
  853.                 high = mid;
  854.             else
  855.                 low = mid + 1;
  856.         }
  857.         if (high < d)  {
  858.             memmove(&linkS[high+1],
  859.                 &linkS[high],
  860.                 sizeof(linkS[0U])
  861.                 *(d-high));
  862.             linkS[high] = D;
  863.         }
  864.     }
  865.     return (int) (flags |= CL_SORTED);
  866. }
  867.  
  868. void * cl::insSort(void * D)
  869. {
  870.     unsigned low, mid, high;
  871.     void * ok;
  872.  
  873. /*
  874.     The current node is left undefined if
  875.     anything fails, otherwise it is set to the
  876.     newly inserted node.
  877. */
  878.  
  879.     curNode = nodes;
  880.     if (!cmP) if ((cmP = DcmP(voidCmP0))
  881.         == voidCmP0) return (void *)0;
  882.     if (!D || nodes >= maxNodes)
  883.         return (void *)0;
  884.     if (!linkS)
  885.         if ((linkS = new void *[limit])
  886.             == (void **)0)
  887.             return (void *)0;
  888.     if (!(flags & CL_SORTED))
  889.         if (!sort())
  890.             return (void *)0;
  891.     low = 0U;
  892.     high = nodes;
  893.     while (low < high)  {
  894.         mid = low + ((high - low) >> 1);
  895.         if ((*cmP)(D,
  896.             linkS[(first+mid)%limit]) <= 0)
  897.             high = mid;
  898.         else
  899.             low = mid + 1;
  900.     }
  901.     if ((ok = atIns(high,D)) != (void *)0)
  902.         curNode = high;
  903.     /*  atIns() resets sorted to zero  */
  904.     flags |= CL_SORTED;
  905.     return ok;
  906. }
  907.  
  908. void * cl::insSortNew(const void * D)
  909. {
  910.     void * cD;
  911.  
  912.     if (D && flags & CL_DNEW)
  913.         if ((cD = Dnew(D)) != (void *)0)
  914.             if (insSort(cD))  {
  915.                 flags |= CL_DNEWED;
  916.                 return cD;
  917.             }
  918.             else
  919.                 Ddelete(cD);
  920.     return (void *)0;
  921. }
  922.  
  923. void * cl::insUnique(void * D)
  924. {
  925.     if (!findFirst(D))
  926.         return insSort(D);
  927.     return (void *)0;
  928. }
  929.  
  930. void * cl::insUniqueNew(const void * D)
  931. {
  932.     if (!findFirst(D))
  933.         return insSortNew(D);
  934.     return (void *)0;
  935. }
  936.  
  937. void * cl::findFirst(const void * K)
  938. {
  939.     unsigned low, mid, high;
  940.     void * D;
  941.  
  942. /*
  943.     The current node is left undefined if
  944.     anything fails, otherwise it is set to the
  945.     newly found node.
  946. */
  947.  
  948.     curNode = nodes;
  949.     if (!cmP) if ((cmP = DcmP(voidCmP0))
  950.         == voidCmP0) return (void *) 0;
  951.     if (!linkS || !K || !nodes)
  952.         return (void *)0;
  953.     if (flags & CL_SORTED)  {
  954.         low = 0U;
  955.         high = nodes;
  956.         while (low < high)  {
  957.             mid = low +
  958.                 ((high - low) >> 1);
  959.             if ((*cmP)(K,linkS[(first+mid)
  960.                 %limit]) <= 0)
  961.                 high = mid;
  962.             else
  963.                 low = mid + 1;
  964.         }
  965.         if (high < nodes)
  966.             if (!(*cmP)(K,D=linkS[(first+
  967.                 high)%limit]))  {
  968.                 curNode = high;
  969.                 return D;
  970.             }
  971.     }
  972.     else  {  /*  linear search!  */
  973.         while ((D = next()) != (void *)0)
  974.             if (!(*cmP)(K,D))
  975.                 return D;
  976.     }
  977.     return (void *)0;
  978. }
  979.  
  980. void * cl::findNext(const void * K)
  981. {
  982.  
  983. /*
  984.     For sorted cls you must first call
  985.     findFirst() to insure consistent results!
  986. */
  987.  
  988.     void * D;
  989.  
  990. /*
  991.     The current node is left undefined if
  992.     anything fails, otherwise it is set to the
  993.     newly found node.
  994. */
  995.  
  996.     if (!cmP)
  997.         cmP = DcmP(voidCmP0);
  998.     if (!linkS || !K || !cmP)  {
  999.         curNode = nodes;
  1000.         return (void *)0;
  1001.     }
  1002.     while ((D = next()) != (void *)0)
  1003.         if (!(*cmP)(K,D))
  1004.             return D;
  1005.         else if (flags & CL_SORTED)  {
  1006.             curNode = nodes;
  1007.             break; /*  Look no further!  */
  1008.         }
  1009.     return (void *)0;
  1010. }
  1011.  
  1012. void * cl::findLast(const void * K)
  1013. {
  1014.     unsigned low, mid, high;
  1015.     void * D;
  1016.  
  1017. /*
  1018.     The current node is left undefined if
  1019.     anything fails, otherwise it is set to the
  1020.     newly found node.
  1021. */
  1022.  
  1023.     curNode = nodes;
  1024.     if (!cmP) if ((cmP = DcmP(voidCmP0))
  1025.         == voidCmP0) return (void *)0;
  1026.     if (!linkS || !K || !nodes)
  1027.         return (void *)0;
  1028.     if (flags & CL_SORTED)  {
  1029.         low = 0U;
  1030.         high = nodes;
  1031.         while (low < high)  {
  1032.             mid = low +
  1033.                 ((high - low) >> 1);
  1034.             if ((*cmP)(K,linkS[(first+mid)
  1035.                 %limit]) < 0)
  1036.                 high = mid;
  1037.             else
  1038.                 low = mid + 1;
  1039.         }
  1040.         if (high < nodes)
  1041.             if (!(*cmP)(K,D=linkS[(first+
  1042.                 high)%limit]))  {
  1043.                 curNode = high;
  1044.                 return D;
  1045.             }
  1046.     }
  1047.     else  {  /*  linear search!  */
  1048.         while ((D = prev()) != (void *)0)
  1049.             if (!(*cmP)(K,D))
  1050.                 return D;
  1051.     }
  1052.     return (void *)0;
  1053. }
  1054.  
  1055. void * cl::findPrev(const void * K)
  1056. {
  1057.  
  1058. /*
  1059.     For sorted cls you must first call
  1060.     findLast() to insure consistent results!
  1061. */
  1062.  
  1063.     void * D;
  1064.  
  1065. /*
  1066.     The current node is left undefined if
  1067.     anything fails, otherwise it is set to the
  1068.     newly found node.
  1069. */
  1070.  
  1071.     if (!cmP)
  1072.         cmP = DcmP(voidCmP0);
  1073.     if (!linkS || !K || !cmP)  {
  1074.         curNode = nodes;
  1075.         return (void *)0;
  1076.     }
  1077.     while ((D = prev()) != (void *)0)
  1078.         if (!(*cmP)(K,D))
  1079.             return D;
  1080.         else if (flags & CL_SORTED)  {
  1081.             curNode = nodes;
  1082.             break; /*  Look no further!  */
  1083.         }
  1084.     return (void *)0;
  1085. }
  1086.  
  1087. unsigned cl::findAll(const void * K)
  1088. {
  1089.     unsigned count = 0U;
  1090.  
  1091.     /*  The current node is left undefined.  */
  1092.  
  1093.     if (findFirst(K))
  1094.         do {
  1095.             count++;
  1096.         } while (findNext(K));
  1097.     return count;
  1098. }
  1099.  
  1100.  
  1101.  
  1102. struct GenericFnCRecord  {
  1103.     GenericFnC fnC;
  1104.     unsigned id;
  1105.     GenericFnCRecord(GenericFnC fnC, unsigned id)
  1106.         { this->fnC = fnC; this->id = id; }
  1107.     ~GenericFnCRecord()  {}
  1108. };
  1109.  
  1110. typedef struct GenericFnCRecord * GenericFnCR;
  1111. #define GenericFnCR0  ((GenericFnCR)0)
  1112.  
  1113. int FunctionRegistry::regFnC(GenericFnC fnC,
  1114.     unsigned id)
  1115. {
  1116.     unsigned i;
  1117.  
  1118.     if (!fnC && !id)  // NULL's id is 0
  1119.         return 1;
  1120.     if ((!fnC && id) || (fnC && !id))
  1121.         return 0;
  1122.     for (i = 0U; i < Nodes(); i++)
  1123.         if (((GenericFnCR)atGet(i))->id
  1124.             == id)
  1125.             break;
  1126.     if (i < Nodes())
  1127.             return 0;
  1128.     GenericFnCR R = new GenericFnCRecord(fnC,id);
  1129.     if (!R)
  1130.         return 0;
  1131.     else if (!insQ((void *)R))  {
  1132.         delete R;
  1133.         return 0;
  1134.     }
  1135.     return 1;
  1136. }
  1137.  
  1138. unsigned FunctionRegistry::fnC_2_ID(GenericFnC fnC)
  1139. {
  1140.     GenericFnCR R;
  1141.     unsigned i;
  1142.  
  1143.     if (!fnC)
  1144.         return 0U;
  1145.     for (i = 0U; (R = (GenericFnCR) atGet(i))
  1146.         != GenericFnCR0; i++)
  1147.         if (R->fnC == fnC)
  1148.             return R->id;
  1149.     return 0U;
  1150. }
  1151.  
  1152. GenericFnC FunctionRegistry::ID_2_fnC(unsigned id)
  1153. {
  1154.     GenericFnCR R;
  1155.     unsigned i;
  1156.  
  1157.     if (!id)
  1158.         return GenericFnC0;
  1159.     for (i = 0U; (R = (GenericFnCR) atGet(i))
  1160.         != GenericFnCR0; i++)
  1161.         if (R->id == id)
  1162.             return R->fnC;
  1163.     return GenericFnC0;
  1164. }
  1165.  
  1166. FunctionRegistry fnCv;
  1167.